public class NumDecodings {

    public static void main(String[] args) {
        NumDecodings numDecodings = new NumDecodings();
        System.out.println(numDecodings.numDecodings("2611055971756562"));
    }

    public int numDecodings(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int[] dp = new int[n];
        dp[0] = chars[0] == '0' ? 0 : 1;
        for (int i = 1; i < n; i++) {
            char c1 = chars[i];
            char c2 = chars[i - 1];
            if (chars[i] != '0') {
                dp[i] += dp[i - 1];
            }
            if (c2 == '1' || (c2 == '2' && c1 <= '6')) {
                dp[i] += i - 2 >= 0 ? dp[i - 2] : 1;
            }
        }
        return dp[n - 1];
    }
}
